#include<iostream>
#include<algorithm>

#include "Graph.h"
#include "virtual_graph.h"

virtual_graph::~virtual_graph(){


};

void virtual_graph::SetupTopology(Graph *graph){
    graph_=graph;
    num_nodes_=graph->NodeSize();
    virtual_adjList=std::vector<std::vector<virtual_link *>>(num_nodes_+1);
};

void virtual_graph::makeVirtualGraph(){
    for(int i=1;i<=num_nodes_;i++){  //节点编号从1开始，储存位置也从1开始
        virtual_link *vir_lk=new virtual_link(i);
        Dfs_virLink(vir_lk,nullptr);
        delete vir_lk;
    }
    return;
}



void virtual_graph::Dfs_virLink(virtual_link *vir_lk,Link *lk){
    if(lk){
        for(int i=0;i<vir_lk->nodes_passed.size();i++){
            if(vir_lk->nodes_passed[i]==lk->ter_id){
                if(isNodeEnd(lk->source_id,vir_lk)){
                    virtual_link *tmp=new virtual_link(vir_lk);
                    if(!isCopy(tmp)){
                        virtual_adjList[vir_lk->source_id].emplace_back(tmp);
                    }else{
                        delete tmp;
                    }
                }
                return;
            }
        }
        std::vector<int> new_C_units=intersection(vir_lk->C_units,lk->C_units);
        int type=graph_->GetNodeType(vir_lk->ter_id);
        if(new_C_units.size()==0 || vir_lk->cost+lk->cost>limit_cost){
            vir_lk->C_units=Omega;
            if(type==1){
                vir_lk->delay_on =100;
            }else if(type==2){
                vir_lk->delay_on =10;
            }else{
                return;
            }
            virtual_link *tmp=new virtual_link(vir_lk);
            if(!isCopy(tmp)){
                virtual_adjList[vir_lk->source_id].emplace_back(tmp);
            }else{
                delete tmp;
            }
            return;
        }else{
            vir_lk->cost += lk->cost;
            vir_lk->nodes_passed.emplace_back(lk->ter_id);
            vir_lk->links_passed.emplace_back(lk);
            vir_lk->ter_id = lk->ter_id;
            vir_lk->C_units=new_C_units;
        }
    } // lk非空
    
    for(Link *link:graph_->GetEgressLinks(vir_lk->ter_id)){
        virtual_link *temp_lk=new virtual_link(vir_lk);

        Dfs_virLink(vir_lk,link);

        vir_lk->cost=temp_lk->cost;
        vir_lk->delay_on=temp_lk->delay_on;
        vir_lk->C_units=temp_lk->C_units;
        vir_lk->ter_id=temp_lk->ter_id;
        vir_lk->nodes_passed=temp_lk->nodes_passed;
        vir_lk->links_passed=temp_lk->links_passed;
        delete temp_lk;
    }
}

Path virtual_graph::pulse_findPath(NodeId from, NodeId to){
    Path p(from,to);
    for(virtual_link *vir_lk:virtual_adjList[to]){
        for(int i=1;i<vir_lk->nodes_passed.size();i++){
            p.node_set.emplace(vir_lk->nodes_passed[i]);
        }
    }
    virtual_link *lk=new virtual_link(from);
    Dfs(to,lk,p);
    delete lk;
    return fianlPath;
}

void virtual_graph::Dfs(NodeId end,virtual_link *edge, Path p){
    if(!judge(edge,p)){
        return;
    }

   
    for(int i=1;i<edge->nodes_passed.size();i++){
        p.path_info.emplace_back(edge->nodes_passed[i]);
        p.delay +=edge->links_passed[i-1]->delay;
    }
    p.path_on.emplace_back(edge->ter_id);

    if(edge->ter_id==end){
        if(p.delay<minDelay){
            minDelay=p.delay;
            fianlPath=p;
        }
        return;
    }

    p.delay +=edge->delay_on;

    if(p.find(edge->ter_id)){
        virtual_link *tmp;
        int min=kMaxValue;
        for(virtual_link *lk:virtual_adjList[edge->ter_id]){
            int sum=0;
            for(int i=1;i<lk->nodes_passed.size();i++){
                sum +=lk->links_passed[i-1]->delay;
                if(lk->nodes_passed[i]==end){
                    if(sum<min){
                        min=sum;
                        tmp=lk;
                    }
                    break;
                }
            }
        }
        p.delay +=min;
        p.path_on.emplace_back(end);
        for(int i=1;i<tmp->nodes_passed.size();i++){
            p.path_info.emplace_back(tmp->nodes_passed[i]);
            if(tmp->nodes_passed[i]==end) break;
        }
        minDelay=p.delay;
        fianlPath=p;
        return;
    }  
    
    for(virtual_link *lk:virtual_adjList[edge->ter_id]){
        Dfs(end, lk,p);
    }

}

bool virtual_graph::judge(virtual_link *edge,Path p){
    if(p.delay>minDelay){
        return false;
    }
    if(intersection(edge->C_units,p.C_units).empty()){
        return false;
    } 
    for(int i=0;i<p.path_info.size();i++){
        for(int j=1;j<edge->nodes_passed.size();j++){
            if(edge->nodes_passed[j]==p.path_info[i]){
                return false;
            }
        }
    }
    return true;
}



std::vector<int> virtual_graph::intersection(std::vector<int> v1, std::vector<int> v2){
    std::unordered_set<int> result_set; // 用于存放结果
    std::unordered_set<int> nums_set(v1.begin(), v1.end());
        for (int num : v2) {
            // 发现v2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
    return std::vector<int>(result_set.begin(), result_set.end());
}

bool virtual_graph::isNodeEnd(NodeId n,virtual_link *vir_lk){
    for(Link *lk:graph_->GetEgressLinks(n)){
        bool flag=true;
        for(int i=0;i<vir_lk->nodes_passed.size();i++){
            if(lk->ter_id==vir_lk->nodes_passed[i]){
                flag=false;
                break;
            }
        }
        if(flag){
            return false;
        }
    }
    return true;
}

bool virtual_graph::isCopy(virtual_link *vir_lk) const{
    int size = virtual_adjList[vir_lk->source_id].size();
    if(size==0) return false;
    virtual_link *tmp=virtual_adjList[vir_lk->source_id][size-1];
    for(int i=0;i<vir_lk->nodes_passed.size();i++){
        if(vir_lk->nodes_passed[i]!=tmp->nodes_passed[i]){
            return false;
        }
    }

    if(vir_lk->ter_id!=tmp->ter_id) return false;

    return true;
}


void virtual_graph::updateVirGraph(Path p){

}



//用于检测构建图是否成功
void virtual_graph::Check(){
    for(int i=1;i<=num_nodes_;i++){
        std::cout<<i<<':'<<std::endl;
        for(virtual_link *lk:virtual_adjList[i]){
            lk->Print();
        }
        std::cout<<std::endl;
    }
}